package com.fanshuai.algorithms.dynamic;

import com.fanshuai.algorithms.datastructure.tree.binarytree.BinaryTree;

import java.util.HashMap;
import java.util.Map;

public class Steel {

    /**
     * 盗贼问题1
     * 你是一个专业的盗贼，计划打劫街道的房屋。每间房内有一定的现金，相邻的房屋有相互连通的防盗系统。
     * 如果相邻的房屋在同一晚上被盗贼闯入，系统会自动报警。给定一个存放房屋金额的非负整数数组，计算在不触动报警装置的
     * 情况下，能盗窃的最高金额
     *
     * 动态规划解法：
     * dp[n]代表从house[1..n]中能盗窃的最高金额
     *
     * dp[n] = max(dp[n-1], house[n-1] + dp[n-2])
     * dp[0] = 0, dp[1] = house[0]
     * @param house
     * @return
     */
    public static int steelCash(int[] house) {
        int len = house.length;
        int[] dp = new int[len + 1];
        dp[0] = 0;
        dp[1] = house[0];

        for (int i = 2; i <= len; i++) {
            dp[i] = Math.max(dp[i - 1], house[i - 1] + dp[i - 2]);
        }

        return dp[len];
    }

    /**
     * 盗贼问题2
     * 你是一个专业的盗贼，计划打劫街道的房屋, 接到的房屋排成了一个环。每间房内有一定的现金，相邻的房屋有相互连通的防盗系统。
     * 如果相邻的房屋在同一晚上被盗贼闯入，系统会自动报警。给定一个存放房屋金额的非负整数数组，计算在不触动报警装置的
     * 情况下，能盗窃的最高金额
     *
     * 房屋排成一个环，可以转化为2个盗贼1子问题。即house[0..n-2]和house[1..n-1]两个子问题
     * @param house
     * @return
     */
    public static int steelCash2(int[] house) {
        int len = house.length;
        int max1 = steelCash0(house, 1, len - 1);
        int max0 = steelCash0(house, 0, len - 2);
        return Math.max(max0, max1);
    }

    private static int steelCash0(int[] house, int start, int end) {
        int len = end + 1 - start;

        int[] dp = new int[len + 1];
        dp[0] = 0;
        dp[1] = house[start];

        for (int i = 2; i <= len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + house[start + i - 1]);
        }
        return dp[len];
    }

    /**
     * 盗贼问题3
     * 你是一个专业的盗贼，计划打劫街道的房屋, 每间房内有一定的现金。
     * 房屋是一个二叉树节后，你不能抢劫相连的房屋
     *
     * 使用递归求解  由于存在重叠子问题，使用备忘录记录
     * @return
     */
    public static int steelCash3(Integer[] houses) {
        BinaryTree.Node node = BinaryTree.buildTreeFromBFS(houses);

        Map<BinaryTree.Node, Integer> map = new HashMap<>();
        return steelFromTree(node, map);
    }

    private static int steelFromTree(BinaryTree.Node node, Map<BinaryTree.Node, Integer> map) {
        if (null == node) {
            return 0;
        }
        if (map.containsKey(node)) {
            return map.get(node);
        }

        int notDo = steelFromTree(node.left, map) + steelFromTree(node.right, map);
        int doIt = node.value;
        if (node.left != null) {
            doIt += steelFromTree(node.left.left, map) + steelFromTree(node.left.right, map);
        }
        if (node.right != null) {
            doIt += steelFromTree(node.right.left, map) + steelFromTree(node.right.right, map);
        }

        return Math.max(notDo, doIt);
    }

    public static void main(String[] args) {
        int[] house1 = {1, 2, 3, 1};
        int[] house2 = {2, 7, 9, 3, 1};

        System.out.println(steelCash(house1));
        System.out.println(steelCash(house2));

        System.out.println(steelCash2(house1));
        System.out.println(steelCash2(house2));

        int[] house3 = {2, 3, 2};
        System.out.println(steelCash(house3));
        System.out.println(steelCash2(house3));

        Integer[] tree = {3, 4, 5, 1, 3, null, 1};
        System.out.println(steelCash3(tree));
    }
}
